#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef int DataType;

//二叉树结点结构定义
typedef struct Node
{
	DataType data;
	struct Node *LChild;
	struct Node *RChild;
}BiTNode,*BiTree;

//创建二叉树(递归)
BiTree CreateBiTreeDG()
{
	DataType item;
	printf("请输入结点数据（-1表示空结点）：");
	scanf("%d",&item);
	if(item==-1){return NULL;}
	else
	{
		BiTree newNode=(BiTree)malloc(sizeof(BiTNode));
		newNode->data=item;
		newNode->LChild=CreateBiTreeDG();
		newNode->RChild=CreateBiTreeDG();
		return newNode;
	}
}

//创建二叉树(非递归)
BiTree CreateBiTreeFDG()
{
	DataType item;
    BiTree root=NULL,*queue=NULL;
    int front=0,rear=0,capacity=100;
	
    queue=(BiTree*)malloc(capacity*sizeof(BiTree));
    printf("请输入根结点数据（-1表示空结点）：");
    scanf("%d", &item);
    if(item!=-1) 
	{
		root=(BiTree)malloc(sizeof(BiTNode));
	    root->data=item;
	    root->LChild=NULL;
	    root->RChild=NULL;
	    queue[rear++]=root;
    }
    while(front<rear) 
	{
	    BiTree current=queue[front++];
	    // 左子节点
	    printf("请输入%d的左子结点数据（-1表示空节点）：",current->data);
	    scanf("%d",&item);
	    if(item!=-1) 
		{
		    BiTree leftChild=(BiTree)malloc(sizeof(BiTNode));
		    leftChild->data = item;
		    leftChild->LChild = NULL;
		    leftChild->RChild = NULL;
		    current->LChild = leftChild;
		    if(rear==capacity) 
			{
			    capacity*= 2;
			    queue=(BiTree*)malloc(capacity*sizeof(BiTree));
			}
		queue[rear++]=leftChild;
	    }
	
	    // 右子节点
	    printf("请输入%d的右子结点数据（-1表示空结点）：",current->data);
	    scanf("%d", &item);
	    if (item!=-1) 
		{
		    BiTree rightChild=(BiTree)malloc(sizeof(BiTNode));
		    rightChild->data = item;
		    rightChild->LChild = NULL;
		    rightChild->RChild = NULL;
		    current->RChild = rightChild;
		    if(rear==capacity) 
			{
			    capacity *= 2;
			    queue = (BiTree*)malloc(capacity * sizeof(BiTree));
			}
	 	queue[rear++]=rightChild;
	    }
	}
	free(queue);
	return root;
}

//递归先序遍历
void PreOrder(BiTree root)
{
	if(root!=NULL)
	{
		printf("%d ",root->data);
	    PreOrder(root->LChild);
	    PreOrder(root->RChild);
	}
}

//递归中序遍历
void InOrder(BiTree root)
{
	if(root!=NULL)
	{
	    InOrder(root->LChild);
	    printf("%d ",root->data);
	    InOrder(root->RChild);
	}
}

//递归后序遍历
void PostOrder(BiTree root)
{
	if(root!=NULL)
	{
	    PostOrder(root->LChild);
	    PostOrder(root->RChild);
	    printf("%d ",root->data);
	}
}

//非递归先序遍历
void PreOrder1(BiTree root)
{
	if(root==NULL){return;}
	BiTree S[100];
	BiTNode *p=root;
	int top=-1;
	do
	{
		if(p!=NULL)
		{
			printf("%d ",root->data);
			top++;S[top]=p;
			p=p->LChild;
		}
		else
		{
			p=S[top];top--;
			p=p->RChild;
		}
	}while(top>-1||p!=NULL);	
}

//非递归中序遍历
void InOrder1(BiTree root)
{
	if(root==NULL){return;}
	BiTree S[100];
	BiTNode *p;
	int top=-1;
	p=root;
	do
	{
		if(p!=NULL)
		{
			top++;S[top]=p;
			p=p->LChild;
		}
		else
		{
			p=S[top];top--;
			printf("%d ",root->data);
			p=p->RChild;
		}
	}while(top>-1||p!=NULL);
}

//非递归后序遍历
void PostOrder1(BiTree root)
{
	if(root==NULL){return;}
	BiTree S[100];
	BiTNode *p,*q;
	int top=-1;
	p=root;q=NULL;
	do
	{
		if(p!=NULL)
		{
			top++;S[top]=p;
			p=p->LChild;
		}
		else
		{
			p=S[top];
			if((p->RChild==NULL)||(p->RChild==q))
			{
				printf("%d ",root->data);
				q=p;
				top--;
				p=NULL;
			}
			else{p=p->RChild;}
		}
	}while(top>-1||p!=NULL);
}

//层次遍历
void levelOrder(BiTree root) {
	if(root==NULL) return;
	BiTree queue[100];
	int front=0,rear=0;
	queue[rear++]=root;
	while(front<rear) 
	{
		BiTree node=queue[front++];
		printf("%d ", node->data);
		if(node->LChild!=NULL) queue[rear++]=node->LChild;
		if(node->RChild!=NULL) queue[rear++]=node->RChild;
	}
}

//求树的深度
int TreeDepth(BiTree bt)
{
	int hl,hr,max;
	if(bt!=NULL)
	{
		hl=TreeDepth(bt->LChild);
		hr=TreeDepth(bt->RChild);
		max=hl>hr?hl:hr;
		return(max+1);
	}
	else return 0;
}

//求结点数
int nodeCount(BiTree T) {
	if(T==NULL) return 0;
	return 1+nodeCount(T->LChild)+nodeCount(T->RChild);
}

//求叶子结点数
int leaf(BiTree root)
{
	int LeafCount;
	if(root==NULL) LeafCount=0;
	else if((root->LChild==NULL)&&(root->RChild==NULL)) LeafCount=1;
	else LeafCount=leaf(root->LChild)+leaf(root->RChild);
	return LeafCount;
}

int main()
{
	BiTree T=NULL;
	int choice1,choice2;
	//一级菜单
	while(1)
	{
		printf("-----二叉树操作一级菜单-----\n");
		printf("1.创建二叉树\n");
		printf("2.遍历二叉树\n");
		printf("3.获取二叉树的属性\n");
		printf("4.退出\n");
		printf("请选择1级菜单操作：");
		scanf("%d",&choice1);
		switch(choice1)
		{
		case 1:
			printf("-----二叉树操作二级菜单-----\n");
			printf("1.递归创建二叉树\n");
			printf("2.非递归创建二叉树\n");
			printf("3.返回一级菜单\n");
			printf("请选择二级菜单操作：");
			scanf("%d",&choice2);
			switch(choice2)
			{
			case 1:
				T=CreateBiTreeDG();
				if(T!=NULL)
				{
					printf("创建好的二叉树层次遍历结果：");
					levelOrder(T);
					printf("\n");
				}
				break;
		    case 2:
				T=CreateBiTreeFDG();
				if(T!=NULL)
				{
					printf("创建好的二叉树层次遍历结果：");
					levelOrder(T);
					printf("\n");
				}
				break;
			default:
				printf("选择错误，请重新选择！\n");
			}while(getchar()!='\n');
            break;
			
		case 3:
			printf("-----二叉树操作二级菜单-----\n");
			printf("1.求树的深度\n");
			printf("2.求叶子结点数\n");
			printf("3.求结点数\n");
			printf("4.返回一级菜单\n");
			printf("请选择二级菜单操作：");
			scanf("%d",&choice2);
			switch(choice2)
			{
			case 1:
				printf("树的深度为：%d\n",TreeDepth(T));
				break;
			case 2:
				printf("叶子结点数为：%d\n",leaf(T));
				break;
			case 3:
				printf("结点数为：%d\n",nodeCount(T));
				break;
			case 4:
				break;
			default:
				printf("选择错误，请重新选择！\n");
			}
		    break;
		case 2:
			printf("-----二叉树操作二级菜单-----\n");
			printf("1.先序遍历（递归）\n");
			printf("2.中序遍历（递归）\n");
			printf("3.后序遍历（递归）\n");
			printf("4.先序遍历（非递归）\n");
			printf("5.中序遍历（非递归）\n");
			printf("6.后序遍历（非递归）\n");
			printf("7.层次遍历\n");
			printf("8.返回一级菜单\n");
			printf("请选择二级菜单操作：");
			scanf("%d",&choice2);
			switch(choice2)
			{
			case 1:
				PreOrder(T);printf("\n");
				break;
			case 2:
				InOrder(T);printf("\n");
				break;
			case 3:
				PostOrder(T);printf("\n");
				break;
			case 4:
				PreOrder1(T);printf("\n");
				break;
			case 5:
				InOrder1(T);printf("\n");
				break;
			case 6:
				PostOrder1(T);printf("\n");
				break;
			case 7:
				levelOrder(T);printf("\n");
				break;
			case 8:
				break;
			default:
				printf("选择错误，请重新选择！\n");
			}
			break;
		case 4:
			exit(0);
		default:
			printf("选择错误，请重新选择！\n");	
		}	
	}	
	return 0;
}
